/*
	现在为对二叉树的一些基本操作,这里实现的是二叉排序树，但不是二叉排序树
	下一步为平衡二叉排序树
	该程序实现了对树的初始化，输出顺序序列，求叶子节点个数，求深度，增加节点
	增加了左右子树的交换，其作用结果位排序的改变。
	
*/
#include <stdio.h>
#include <malloc.h>

typedef struct BiTree{
	int data;
	struct BiTree *left, *right;
} BiTree;

BiTree *initial(){
	BiTree *root = (BiTree*)malloc(sizeof(BiTree));
		root -> data = 78;		//该书头节点有数据
		root -> left =  root -> right = NULL;
	return root;
}
	
void addData(BiTree *root, int in){

	if(root -> data > in){
		if(root -> left)
			addData(root -> left, in);
		else {
			 BiTree *new = (BiTree*)malloc(sizeof(BiTree));
			 root -> left = new; 
			 new -> data = in;
			 new -> left = new -> right = NULL;
		}	
	} else {
		if (root -> right)
			addData(root -> right, in);
		else { 
			BiTree *new = (BiTree *)malloc(sizeof(BiTree));
			root -> right = new;
			new -> data = in;
			new -> left = new -> right = NULL;
		}
	}
}
	
void printTree(BiTree *root){			//中序遍历，输出顺序上升序列

	if (root -> left) printTree(root -> left);
	
	printf("%d\t", root -> data);

	if(root -> right) printTree(root -> right);
}

int getLeaf(BiTree *root){
	
	if (root == NULL) 
		return 0;
	else if (root->left == NULL && root->right == NULL) 
		return 1;
	else 
		return getLeaf(root->left) + getLeaf(root->right);
}

int max(int a, int b){
	return a > b ? a : b;
}

int getDepth (BiTree *root) {
	
	if (root == NULL) return 0;
	else if (root->left == NULL && root->right == NULL)
		return 1;
	else 
		return 1 + max(getDepth(root->left), getDepth(root->right));
}

void input(BiTree *root, int nul){
	
	for(int i = 0; i < nul; i++){
		int temp;
		scanf("%d",&temp); 
		addData(root, temp);
	}
}

void L2R(BiTree *root){
	if (root == NULL) 
		return ;
	else {
		BiTree *temp = root->left;
		root->left = root->right;
		root->right = temp;		
	}
	L2R(root->left);
	L2R(root->right);
}

int
main(){

	BiTree *root = initial();
	
	int nul;
	scanf("%d", &nul);
	input(root, nul);

	printTree(root);

	printf("%d\n", getLeaf(root));

	printf("%d", getDepth(root));
	
	L2R(root);
	
	printTree(root);
}
